#include <iostream>
using namespace std;



  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
 
  struct TreeNode {
     int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
TreeNode *sortedListToBST(ListNode *head);

int main(){

    ListNode a(1);
    TreeNode *pNode = sortedListToBST(&a);


    return 0;
}

int GetLength(ListNode *head){
    int length = 0;
    ListNode *cur = head;
    while(cur){
        ++length; 
        cur = cur->next;
    }
    return length;
}

TreeNode *BuildSubTree(ListNode *head, int length){
    if(length == 0)
        return NULL;
    int mid = length/2;
    int cur = 0;
    ListNode *pMid = head;
    while(cur != mid){
        pMid = pMid->next;
        ++cur;
    }
    TreeNode *pRoot = new TreeNode(pMid->val);
    //left
    if(mid!=0){
        pRoot->left = BuildSubTree(head, mid);
    }
    //right
    if(mid!=length-1){
        pRoot->right = BuildSubTree(pMid->next, length-mid-1);
    }
    return pRoot;
}

TreeNode *sortedListToBST(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!head)
        return NULL;
    int length = GetLength(head);
    return BuildSubTree(head, length);
}